<html>
<head><meta charset="utf-8"><title>Proptest generate sorted vec · general · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/index.html">general</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html">Proptest generate sorted vec</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="191313482"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313482" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313482">(Mar 20 2020 at 23:04)</a>:</h4>
<p><span class="user-mention" data-user-id="126931">@centril</span> do you have any suggestions on how I could generate an arbitrary <code>Vec&lt;Option&lt;T&gt;&gt;</code> where all of the <code>Some</code> values are sorted?</p>
<p>Said another way, a sorted <code>Vec</code> with <code>None</code>s scattered throughout.</p>



<a name="191313664"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313664" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313664">(Mar 20 2020 at 23:06)</a>:</h4>
<p>My current path is an arbitrary vec that I've sorted, then I map over that with <code>prop_perturb</code>, convert it into an iterator, then generate a random number of <code>None</code>s for each step. This works-ish, but doesn't have great shrinking.</p>



<a name="191313671"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313671" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313671">(Mar 20 2020 at 23:06)</a>:</h4>
<p><span class="user-mention" data-user-id="116155">@Jake Goulding</span> does the vector need to be sorted across <code>None</code>s?</p>



<a name="191313695"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313695" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313695">(Mar 20 2020 at 23:07)</a>:</h4>
<p>Or is  <code>[S(1), None, S(0)]</code> valid?</p>



<a name="191313701"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313701" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313701">(Mar 20 2020 at 23:07)</a>:</h4>
<p>I'm not 100% I know what you mean. This would be a valid result: <code>vec![None, Some(1), None, None, None, Some(2)]</code></p>



<a name="191313776"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313776" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313776">(Mar 20 2020 at 23:08)</a>:</h4>
<p>(modulo ascending/descending — that should be trivial <span aria-label="wink" class="emoji emoji-1f609" role="img" title="wink">:wink:</span>)</p>



<a name="191313800"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313800" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313800">(Mar 20 2020 at 23:08)</a>:</h4>
<p>another example then: <code>[S(0), N, S(1), N, S(0)]</code></p>



<a name="191313816"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313816" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313816">(Mar 20 2020 at 23:09)</a>:</h4>
<p>in other words, is <code>None</code> a boundary for sorting?</p>



<a name="191313855"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313855" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313855">(Mar 20 2020 at 23:09)</a>:</h4>
<p>Ah, gotcha. No, I do not want that.</p>



<a name="191313936"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313936" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313936">(Mar 20 2020 at 23:10)</a>:</h4>
<p>Another tack would be if there was a way I could sort the <code>Vec&lt;Option&lt;T&gt;&gt;</code> leaving all of the <code>None</code>s in place.</p>



<a name="191313942"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313942" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313942">(Mar 20 2020 at 23:10)</a>:</h4>
<p>that's what I would do</p>



<a name="191313968"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313968" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313968">(Mar 20 2020 at 23:11)</a>:</h4>
<p>... but I don't actually know how to do that ;-)</p>



<a name="191313976"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313976" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313976">(Mar 20 2020 at 23:11)</a>:</h4>
<p>Like, I know that's not proptest, but my brain isn't braining a way to do that in Rust</p>



<a name="191313981"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313981" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313981">(Mar 20 2020 at 23:11)</a>:</h4>
<p><span class="user-mention" data-user-id="116155">@Jake Goulding</span>  what happens if you use a stable sort and deem <code>None</code> equal to anything?</p>



<a name="191313998"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191313998" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191313998">(Mar 20 2020 at 23:12)</a>:</h4>
<p>I'll whip up a playground and see.</p>



<a name="191314204"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191314204" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191314204">(Mar 20 2020 at 23:15)</a>:</h4>
<p>Looks like that treats the <code>None</code> as boundaries. <a href="https://play.integer32.com/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=3f3356592813dea501c31110446169b4" target="_blank" title="https://play.integer32.com/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=3f3356592813dea501c31110446169b4">https://play.integer32.com/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=3f3356592813dea501c31110446169b4</a></p>



<a name="191314211"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191314211" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191314211">(Mar 20 2020 at 23:15)</a>:</h4>
<p>yea, <a href="https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=23be3c5dc4c67795852866d122904872" target="_blank" title="https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=23be3c5dc4c67795852866d122904872">https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=23be3c5dc4c67795852866d122904872</a> is my version</p>



<a name="191314263"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191314263" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191314263">(Mar 20 2020 at 23:16)</a>:</h4>
<p><span class="user-mention" data-user-id="116155">@Jake Goulding</span> what if you change your requirements <span aria-label="upside down" class="emoji emoji-1f643" role="img" title="upside down">:upside_down:</span>  :D</p>



<a name="191314308"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191314308" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191314308">(Mar 20 2020 at 23:17)</a>:</h4>
<p>So, I said <code>Option</code>, but it's actually <code>Poll</code> — this is for mimicking a stream that returns sorted data but that might not be ready for a number of calls.</p>



<a name="191314326"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191314326" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191314326">(Mar 20 2020 at 23:18)</a>:</h4>
<p>So solving that is my goal and real requirements ;-)</p>



<a name="191314366"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191314366" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191314366">(Mar 20 2020 at 23:18)</a>:</h4>
<p>isomorphic, so same thing :P</p>



<a name="191314390"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191314390" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191314390">(Mar 20 2020 at 23:18)</a>:</h4>
<p>exactly, and I went with <code>Option</code> because it's more familiar</p>



<a name="191314644"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191314644" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191314644">(Mar 20 2020 at 23:22)</a>:</h4>
<p><span class="user-mention" data-user-id="116155">@Jake Goulding</span>  here's a different idea that might be worse, who knows:  Generate a <code>(elems: Vec&lt;T&gt;, insertions: Vec&lt;(where: usize, number: usize)&gt;)</code>, sort <code>elems</code>, throw away anything in <code>insertions</code> which would be out of bounds in <code>elems</code>, and then insert <code>number</code> of <code>None</code>s at <code>elems[where]</code></p>



<a name="191314665"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191314665" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191314665">(Mar 20 2020 at 23:22)</a>:</h4>
<p>the throwing away avoids <code>prop_flat_map</code></p>



<a name="191315023"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191315023" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191315023">(Mar 20 2020 at 23:28)</a>:</h4>
<p>I'm not actually using <code>prop_flat_map</code> — just <code>Iterator::flat_map</code>:</p>
<div class="codehilite"><pre><span></span><span class="w">    </span><span class="k">fn</span> <span class="nf">arb_sorted_data</span><span class="o">&lt;</span><span class="n">T</span>: <span class="nc">Arbitrary</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="nb">Ord</span><span class="o">&gt;</span><span class="p">()</span><span class="w"> </span>-&gt; <span class="nc">impl</span><span class="w"> </span><span class="n">Strategy</span><span class="o">&lt;</span><span class="n">Value</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nb">Vec</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;&gt;</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="n">any</span>::<span class="o">&lt;</span><span class="nb">Vec</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;&gt;</span><span class="p">().</span><span class="n">prop_map</span><span class="p">(</span><span class="o">|</span><span class="k">mut</span><span class="w"> </span><span class="n">d</span><span class="o">|</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="n">d</span><span class="p">.</span><span class="n">sort</span><span class="p">();</span><span class="w"></span>
<span class="w">            </span><span class="n">d</span><span class="w"></span>
<span class="w">        </span><span class="p">})</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>

<span class="w">    </span><span class="sd">/// Adds a small arbitrary number of `Poll::Pending` values before</span>
<span class="w">    </span><span class="sd">/// and after each existing sorted value.</span>
<span class="w">    </span><span class="k">fn</span> <span class="nf">arb_proto_stream</span><span class="o">&lt;</span><span class="n">T</span>: <span class="nc">Arbitrary</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="nb">Ord</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="nb">Clone</span><span class="o">&gt;</span><span class="p">()</span><span class="w"> </span>-&gt; <span class="nc">impl</span><span class="w"> </span><span class="n">Strategy</span><span class="o">&lt;</span><span class="n">Value</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">ProtoStream</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;&gt;</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="kd">let</span><span class="w"> </span><span class="n">max_pending_in_a_row</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">10</span><span class="p">;</span><span class="w"></span>

<span class="w">        </span><span class="n">arb_sorted_data</span><span class="p">().</span><span class="n">prop_perturb</span><span class="p">(</span><span class="k">move</span><span class="w"> </span><span class="o">|</span><span class="n">values</span><span class="p">,</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">rng</span><span class="o">|</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="kd">let</span><span class="w"> </span><span class="n">original</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">values</span><span class="p">.</span><span class="n">clone</span><span class="p">();</span><span class="w"></span>

<span class="w">            </span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">poll_values</span>: <span class="nb">Vec</span><span class="o">&lt;</span><span class="n">_</span><span class="o">&gt;</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">values</span><span class="p">.</span><span class="n">into_iter</span><span class="p">().</span><span class="n">flat_map</span><span class="p">(</span><span class="o">|</span><span class="n">v</span><span class="o">|</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                </span><span class="kd">let</span><span class="w"> </span><span class="n">n_pending</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">rng</span><span class="p">.</span><span class="n">gen_range</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="n">max_pending_in_a_row</span><span class="p">);</span><span class="w"></span>
<span class="w">                </span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">results</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">vec</span><span class="o">!</span><span class="p">[</span><span class="n">Poll</span>::<span class="n">Pending</span><span class="p">;</span><span class="w"> </span><span class="n">n_pending</span><span class="p">];</span><span class="w"></span>
<span class="w">                </span><span class="n">results</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">Poll</span>::<span class="n">Ready</span><span class="p">(</span><span class="n">v</span><span class="p">));</span><span class="w"></span>
<span class="w">                </span><span class="n">results</span><span class="w"></span>
<span class="w">            </span><span class="p">}).</span><span class="n">collect</span><span class="p">();</span><span class="w"></span>

<span class="w">            </span><span class="kd">let</span><span class="w"> </span><span class="n">n_pending</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">rng</span><span class="p">.</span><span class="n">gen_range</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="n">max_pending_in_a_row</span><span class="p">);</span><span class="w"></span>
<span class="w">            </span><span class="n">poll_values</span><span class="p">.</span><span class="n">extend</span><span class="p">(</span><span class="n">vec</span><span class="o">!</span><span class="p">[</span><span class="n">Poll</span>::<span class="n">Pending</span><span class="p">;</span><span class="w"> </span><span class="n">n_pending</span><span class="p">]);</span><span class="w"></span>

<span class="w">            </span><span class="n">ProtoStream</span><span class="w"> </span><span class="p">{</span><span class="w"> </span><span class="n">original</span><span class="p">,</span><span class="w"> </span><span class="n">poll_values</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w">        </span><span class="p">})</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
</pre></div>



<a name="191315102"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191315102" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191315102">(Mar 20 2020 at 23:30)</a>:</h4>
<p><span class="user-mention" data-user-id="116155">@Jake Goulding</span> yeah sure; my mention of flat mapping is unrelated to your current thing</p>



<a name="191315535"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191315535" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191315535">(Mar 20 2020 at 23:36)</a>:</h4>
<p><span class="user-mention" data-user-id="116155">@Jake Goulding</span>  how about this: <a href="https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=ff7bfe6a1adf92c82202a4603f67fa60" target="_blank" title="https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=ff7bfe6a1adf92c82202a4603f67fa60">https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=ff7bfe6a1adf92c82202a4603f67fa60</a></p>



<a name="191315711"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191315711" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191315711">(Mar 20 2020 at 23:39)</a>:</h4>
<p>basically, selection sort seems to be perfect for this since it will keep scanning for things ahead that might be smaller, as opposed to fixating on two things</p>



<a name="191315714"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191315714" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191315714">(Mar 20 2020 at 23:39)</a>:</h4>
<p>Thanks. I'll give a look / try after dinner. <span aria-label="heart" class="emoji emoji-2764" role="img" title="heart">:heart:</span></p>



<a name="191315723"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191315723" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191315723">(Mar 20 2020 at 23:39)</a>:</h4>
<p>Enjoy <span aria-label="food" class="emoji emoji-1f372" role="img" title="food">:food:</span>  <span aria-label="slight smile" class="emoji emoji-1f642" role="img" title="slight smile">:slight_smile:</span></p>



<a name="191316141"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191316141" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191316141">(Mar 20 2020 at 23:44)</a>:</h4>
<p>N.B. selection sort is O(n^2), but works well on smaller inputs</p>



<a name="191316178"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191316178" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191316178">(Mar 20 2020 at 23:45)</a>:</h4>
<p>so it should work well for <code>any::&lt;Vec&lt;T&gt;&gt;()</code>, but if you start jacking up the size into 100'000s or so or millions things will go slower :P</p>



<a name="191316398"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191316398" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191316398">(Mar 20 2020 at 23:49)</a>:</h4>
<p>though at that point I suspect the selection sort is the least of your problems <span aria-label="joy" class="emoji emoji-1f602" role="img" title="joy">:joy:</span></p>



<a name="191342890"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191342890" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191342890">(Mar 21 2020 at 12:14)</a>:</h4>
<p>I’m wondering how much that differs from the concepts in <code>sort_by_cached_key</code> <a href="https://doc.rust-lang.org/src/alloc/slice.rs.html#331-375" target="_blank" title="https://doc.rust-lang.org/src/alloc/slice.rs.html#331-375">https://doc.rust-lang.org/src/alloc/slice.rs.html#331-375</a></p>



<a name="191357690"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191357690" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191357690">(Mar 21 2020 at 17:47)</a>:</h4>
<p>And folk over in Stack Overflow chat suggest something like</p>
<div class="codehilite"><pre><span></span><span class="w">    </span><span class="k">fn</span> <span class="nf">sort_present_values</span><span class="o">&lt;</span><span class="n">T</span>: <span class="nb">Ord</span><span class="o">&gt;</span><span class="p">(</span><span class="n">d</span>: <span class="kp">&amp;</span><span class="nc">mut</span><span class="w"> </span><span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">Option</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;&gt;</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">values</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">vec</span><span class="o">!</span><span class="p">[];</span><span class="w"></span>
<span class="w">        </span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">indices</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">vec</span><span class="o">!</span><span class="p">[];</span><span class="w"></span>

<span class="w">        </span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="n">v</span><span class="p">)</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">d</span><span class="p">.</span><span class="n">iter_mut</span><span class="p">()</span><span class="w"> </span><span class="p">.</span><span class="n">enumerate</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="k">if</span><span class="w"> </span><span class="kd">let</span><span class="w"> </span><span class="nb">Some</span><span class="p">(</span><span class="n">v</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">v</span><span class="p">.</span><span class="n">take</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                </span><span class="n">values</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">v</span><span class="p">);</span><span class="w"></span>
<span class="w">                </span><span class="n">indices</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">i</span><span class="p">);</span><span class="w"></span>
<span class="w">            </span><span class="p">}</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>

<span class="w">        </span><span class="n">values</span><span class="p">.</span><span class="n">sort</span><span class="p">();</span><span class="w"></span>

<span class="w">        </span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="n">v</span><span class="p">,</span><span class="w"> </span><span class="n">i</span><span class="p">)</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">values</span><span class="p">.</span><span class="n">into_iter</span><span class="p">().</span><span class="n">zip</span><span class="p">(</span><span class="n">indices</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nb">Some</span><span class="p">(</span><span class="n">v</span><span class="p">);</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
</pre></div>



<a name="191381482"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191381482" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> centril <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191381482">(Mar 22 2020 at 05:30)</a>:</h4>
<p><span class="user-mention" data-user-id="116155">@Jake Goulding</span> seems like a fine way to do it; at least in terms of complexity you get  <code>O(n log n)</code>, but on the other hand, there's more allocating back and forth</p>



<a name="191502586"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191502586" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191502586">(Mar 23 2020 at 16:50)</a>:</h4>
<p>And of course now the requirements have changed. Now all the <code>Some</code> values need to be unique. Sigh.</p>



<a name="191504701"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191504701" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191504701">(Mar 23 2020 at 17:04)</a>:</h4>
<p>I wonder if it would be simpler to create a <code>Vec&lt;T&gt;</code> of length N and a <code>Vec&lt;usize&gt;</code> of  length N+1 and then zip them, mapping the first to <code>Some</code> and the second to <code>usize</code> <code>None</code>s.</p>



<a name="191504761"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191504761" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191504761">(Mar 23 2020 at 17:04)</a>:</h4>
<p>Then we could use a <code>BTreeSet</code> instead of the first vec and get the sorted / unique for free</p>



<a name="191504808"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Proptest%20generate%20sorted%20vec/near/191504808" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Proptest.20generate.20sorted.20vec.html#191504808">(Mar 23 2020 at 17:05)</a>:</h4>
<p>It's closer to my original idea, but avoids the direct RNG usage</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>